package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-20 13:34:01
 */
class Q0079_WordSearch {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean exist(char[][] board, String word) {
            return process(board, 0, 0, word, 0);
        }

        private boolean process(char[][] board, int bi, int bj, String word, int wi) {
            if (bi == board.length || bj == board[0].length) return false;

            if (wi == word.length()) return true;

            if (wi == 0) {
                for (int i = bi; i < board.length; i++) {
                    for (int j = bj; j < board[0].length; j++) {
                        if (board[i][j] == word.charAt(wi)) {
                            char c = board[i][j];
                            board[i][j] = ' ';
                            if (process(board, i, j, word, 1)) return true;
                            board[i][j] = c;
                        }
                    }
                }
            } else {
                char c = board[bi][bj];
                board[bi][bj] = ' ';
                if (bi > 0 && board[bi - 1][bj] == word.charAt(wi)) {
                    if (process(board, bi - 1, bj, word, wi + 1)) return true;
                }
                if (bi < board.length - 1 && board[bi + 1][bj] == word.charAt(wi)) {
                    if (process(board, bi + 1, bj, word, wi + 1)) return true;
                }
                if (bj > 0 && board[bi][bj - 1] == word.charAt(wi)) {
                    if (process(board, bi, bj - 1, word, wi + 1)) return true;
                }
                if (bj < board[0].length - 1 && board[bi][bj + 1] == word.charAt(wi)) {
                    if (process(board, bi, bj + 1, word, wi + 1)) return true;
                }
                board[bi][bj] = c;
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0079_WordSearch().new Solution();
        System.out.println(solution.exist(new char[][]{{'C', 'A', 'A'}, {'A', 'A', 'A'}, {'B', 'C', 'D'}}, "AAB"));
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED"));
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "SEE"));
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCB"));
    }
}